Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"
  7. Given n and k, return the k-th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution:

  1. public class Solution {
  2.   public String getPermutation(int n, int k) {
  3.     // step 1. prepare the number sequence
  4.     List<Integer> nums = new ArrayList<Integer>();
  5.     for (int i = 1; i <= n; i++) {
  6.       nums.add(i);
  7.     }
  9.     // step 2. calculate (n-1)!
  10.     int[] f = new int[n];
  11.     f[0] = 1;
  12.     for (int i = 1; i < n; i++) {
  13.       f[i] = f[i - 1] * i; 
  14.     }
  16.     // step 3. calculate each digit, total n digits
  17.     StringBuilder sb = new StringBuilder();
  19.     k--;
  20.     while (n > 0) {
  21.       int p = k  / f[n - 1];
  23.       sb.append(nums.get(p));
  24.       nums.remove(p);
  26.       k = k % f[n - 1];
  28.       n--;
  29.     }
  31.     return sb.toString();
  32.   }
  33. }